package com.tping.leetcode;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 *
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 *
 */
public class Solution_0074 {


    public boolean searchMatrix(int[][] matrix, int target) {

        int i = matrix.length - 1, j = 0;

        while (i >= 0 && j < matrix[0].length ){
            if( matrix[i][j] > target)
                i --;
            else if( matrix[i][j] < target )
                j ++;
            else
                return true;
        }

        return false;
    }

    public static void main(String[] args){
        Solution_0074 solution = new Solution_0074();

        int[][] matrix = {
                {1,3,5,7},
                {10,11,16,20},
                {23,30,34,60}
        };
        boolean searchMatrix = solution.searchMatrix(matrix, 16);

        System.out.println("二维矩阵中搜索12是否存在：" + searchMatrix);
    }
}
